#pragma once

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <map>

const int border = 3;


std::vector<int> Integrize(const std::vector<std::string>& sequence, std::map<std::string, int> *integrizing_map) {
    std::vector<int> result;
    for (int i=0; i<sequence.size(); i++) {
        result.push_back(integrizing_map->insert(std::pair<std::string, int>(sequence[i], 
                        integrizing_map->size())).first->second);
    }
    return result;
}



struct Point{
    int x_;
    int y_;
    Point(int x, int y) :  x_(x), y_(y) {}
};


class Massiv {

public:
    Massiv(const int min_index, const int max_index) : min_index_(min_index), max_index_(max_index), 
                        massiv_(min_index + max_index + border, -1) { }

    int& operator[] (int k) {
        return massiv_[min_index_ + 1 + k];
    }

    int GetMinIndex() const { 
        return (-min_index_);
    }
    int GetMaxIndex() const { 
        return max_index_;
    }

private:
    int min_index_;
    int max_index_;
    std::vector<int> massiv_;

};

template<class iterator>
class Sequence {
public:

    Sequence(iterator begin, iterator end) : 
        begin_(begin), end_(end), 
                length_(distance(begin, end)) {}

    iterator GetBegin() const {
        return begin_;
    }

    iterator GetEnd() const {
        return end_;
    }
  
    int GetLength() const {
        return length_;
    }


private:

    iterator begin_;
    iterator end_;
    int length_;
};

template<class iterator>
int MaxCommonPrefix(const Sequence<iterator>& first_sequence, const Sequence<iterator>& second_sequence) {
    int answer = 0;
    iterator first_begin = first_sequence.GetBegin();
    iterator second_begin = second_sequence.GetBegin();
    iterator first_end = first_sequence.GetEnd();
    iterator second_end = second_sequence.GetEnd();

    while (first_begin != first_end && second_begin != second_end) {
        if (*first_begin != *second_begin) return answer;
        answer++;
        first_begin++;
        second_begin++;
    }
    return answer;
}


template<class iterator>
void OneIterationOfAlgorythm(const Sequence<iterator>& first_sequence, 
                const Sequence<iterator>& second_sequence, Massiv* diag, int distance_between_sequences) {
    
    int first_sequence_length = first_sequence.GetLength();
    int second_sequence_length = second_sequence.GetLength();

    int left_border = std::min(distance_between_sequences, second_sequence_length);
    if (left_border % 2 != distance_between_sequences % 2) left_border--;
    int right_border = std::min(distance_between_sequences, first_sequence_length);
    if (right_border % 2 != distance_between_sequences % 2) right_border--;


    for (int diag_number = -left_border; diag_number <= right_border; diag_number += 2) {

        (*diag)[diag_number] = std::max((*diag)[diag_number + 1], (*diag)[diag_number - 1] + 1);
        (*diag)[diag_number] = std::min((*diag)[diag_number], first_sequence_length);
        (*diag)[diag_number] = std::min((*diag)[diag_number], diag_number + second_sequence_length);

        if ((second_sequence_length > (*diag)[diag_number] - diag_number) && 
                        (first_sequence_length > (*diag)[diag_number])) {

            iterator new_first_begin = first_sequence.GetBegin() + (*diag)[diag_number];
            iterator new_second_begin = second_sequence.GetBegin() + ((*diag)[diag_number] - diag_number);

            int prefix = MaxCommonPrefix(Sequence<iterator>(new_first_begin,
                 first_sequence.GetEnd()) , Sequence<iterator>(new_second_begin, second_sequence.GetEnd()));

            (*diag)[diag_number] += prefix;
        }
    }
}


template<class iterator>
int FindDistanceBetweenSequences(const Sequence<iterator>& first_sequence, 
                                        const Sequence<iterator>& second_sequence) {

    int first_sequence_length = first_sequence.GetLength();
    int second_sequence_length = second_sequence.GetLength();

    Massiv diag(second_sequence_length, first_sequence_length);
    diag[0] = MaxCommonPrefix(first_sequence, second_sequence);

    if ((first_sequence_length == second_sequence_length) && (first_sequence_length == diag[0])) return 0;

    for (int distance_between_sequences = 1; ; ++distance_between_sequences) {
        OneIterationOfAlgorythm(first_sequence, second_sequence, &diag, distance_between_sequences);

        int min_meeting_diag_number = - std::min(distance_between_sequences, second_sequence_length + 
                        ((second_sequence_length - distance_between_sequences) % 2));
        int max_meeting_diag_number = std::min(distance_between_sequences, first_sequence_length + 
                        ((first_sequence_length - distance_between_sequences) % 2));

        for (int diag_number = min_meeting_diag_number; diag_number <= max_meeting_diag_number; 
                diag_number += 2) { 
            if (diag[diag_number] == first_sequence_length && 
                        diag[diag_number] - diag_number == second_sequence_length) {
            return distance_between_sequences;
            }
        }
    }
    return 0;
}


template<class iterator>
Point FindOverlapPoint(int distance_between_two_sequences, const Sequence<iterator>& first_sequence, 
                                const Sequence<iterator>& second_sequence) {


    if (distance_between_two_sequences == 0) {
        return Point(0, 0);
    }

    int first_sequence_length = first_sequence.GetLength();
    int second_sequence_length = second_sequence.GetLength();

    int middle = ((distance_between_two_sequences + 1) / 2);

    Massiv diag_down(std::max(second_sequence_length, middle), std::max(first_sequence_length, middle));
    diag_down[0] = MaxCommonPrefix(first_sequence, second_sequence);

    std::reverse_iterator<iterator> first_begin_reverse(first_sequence.GetBegin());
    std::reverse_iterator<iterator> second_begin_reverse(second_sequence.GetBegin());
    std::reverse_iterator<iterator> first_end_reverse(first_sequence.GetEnd());
    std::reverse_iterator<iterator> second_end_reverse(second_sequence.GetEnd());

    Massiv diag_up(std::max(second_sequence_length, middle), std::max(first_sequence_length, middle));

    Sequence<std::reverse_iterator<iterator> > reversed_first_sequence(first_end_reverse, first_begin_reverse);
    Sequence<std::reverse_iterator<iterator> > reversed_second_sequence(second_end_reverse, second_begin_reverse);

    diag_up[0] = MaxCommonPrefix(reversed_first_sequence, reversed_second_sequence);


    for (int i = 1; i <= middle; ++i) { 
        OneIterationOfAlgorythm(first_sequence, second_sequence,  &diag_down, i);
    }

    for (int i = 1; i <= distance_between_two_sequences - middle; ++i) {
        OneIterationOfAlgorythm(reversed_first_sequence, reversed_second_sequence, &diag_up, i);
    }

    int min_meeting_diag_number = -std::min(middle, second_sequence_length + 1);
    int max_meeting_diag_number = std::min(middle, first_sequence_length + 1);

    for (int diag_number = std::min(middle, first_sequence_length + ((first_sequence_length - diag_number) % 2)); 
                diag_number >= -std::min(middle, second_sequence_length + 
                        ((second_sequence_length - diag_number) % 2)); --diag_number) {

        if (diag_down[diag_number] + diag_up[(first_sequence_length - second_sequence_length) - diag_number] 
                                        >= first_sequence_length) {

            return Point(diag_down[diag_number], diag_down[diag_number] - diag_number);
        }
    }
}

template<class iterator>
void GetCommonStringsNumbersImplementation(int distance_between_two_sequences, std::vector<Point> &common_strings, 
                        int distance_to_first_begin, int distance_to_second_begin, 
                        const Sequence<iterator>& first_sequence, const Sequence<iterator>& second_sequence) {

    int first_sequence_length = first_sequence.GetLength();
    int second_sequence_length = second_sequence.GetLength();

    iterator first_begin = first_sequence.GetBegin();
    iterator second_begin = second_sequence.GetBegin();
    iterator first_end = first_sequence.GetEnd();
    iterator second_end = second_sequence.GetEnd();

    if (first_begin == first_end || second_begin == second_end) return;

    if (distance_between_two_sequences == 0) {
        for (int i = 0; i < first_sequence_length; i++) {
            Point new_pair(distance_to_first_begin + i, distance_to_second_begin + i);
            common_strings.push_back(new_pair);
        }
        return;
    }
    Point tochka = FindOverlapPoint(distance_between_two_sequences, first_sequence, second_sequence);

    // if we won't process the case (distance_between_two_sequences == 1), middle_length (defined further) will
    // be equal to 0, so the second branch of recursion will call GetCommonStringsNumbersImplementation with
    // the same parameters, as current call, and there will be a circle.
    if (distance_between_two_sequences == 1) {

        while (*first_begin == *second_begin) {
            Point new_pair(distance_to_first_begin, distance_to_second_begin);
            common_strings.push_back(new_pair);
            distance_to_first_begin++;   distance_to_second_begin++;
            first_begin++;   second_begin++;
        }

        if (first_sequence_length < second_sequence_length) {
            distance_to_second_begin++;   second_begin++;
        } else {
            distance_to_first_begin++;   first_begin++;
        }

        if (first_begin != first_end && second_begin != second_end) {
            while (first_begin != first_end && second_begin != second_end && *first_begin == *second_begin ) {
                Point new_pair(distance_to_first_begin, distance_to_second_begin);
                common_strings.push_back(new_pair);
                distance_to_first_begin++;   distance_to_second_begin++;
                first_begin++;   second_begin++;
            }
        }
        return;

    }

    int middle_length = (distance_between_two_sequences + 1) / 2;

    Sequence<iterator> new_first_sequence(first_begin, first_begin + tochka.x_); 
    Sequence<iterator> new_second_sequence(second_begin, second_begin + tochka.y_);

    GetCommonStringsNumbersImplementation (middle_length, common_strings, distance_to_first_begin,
        distance_to_second_begin, new_first_sequence, new_second_sequence);


    if (!(first_begin + tochka.x_ == first_end || second_begin + tochka.y_ == second_end)) {

        new_first_sequence = Sequence<iterator>(first_begin + tochka.x_, first_end);
 
        new_second_sequence = Sequence<iterator>(second_begin + tochka.y_, second_end);

        GetCommonStringsNumbersImplementation (distance_between_two_sequences - middle_length, common_strings,
                        distance_to_first_begin + tochka.x_, distance_to_second_begin + tochka.y_,
                                 new_first_sequence, new_second_sequence);
    }
}


std::vector<Point> GetCommonStringsNumbers(const std::vector<std::string>& first_sequence_string, 
                        const std::vector<std::string>& second_sequence_string) {

    std::map<std::string, int> integrizing_map;
    std::vector<int> first_sequence_integrized = Integrize(first_sequence_string, &integrizing_map);
    std::vector<int> second_sequence_integrized = Integrize(second_sequence_string, &integrizing_map);

    Sequence<std::vector<int> :: iterator> first_sequence(first_sequence_integrized.begin(),
                        first_sequence_integrized.end());
    Sequence<std::vector<int> :: iterator> second_sequence(second_sequence_integrized.begin(),
                        second_sequence_integrized.end());

    int distance_between_two_sequences = FindDistanceBetweenSequences(first_sequence, second_sequence);
    std::vector<Point> common_strings;
    GetCommonStringsNumbersImplementation(distance_between_two_sequences, common_strings, 0, 0, 
                                first_sequence, second_sequence);
    return common_strings;

}

